package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * tree
 * 655. 输出二叉树
 *
 * @author liw
 * @version 1.0
 * @date 2021/7/27 16:09
 */
public class PrintTree {

    public static void main(String[] args) {
        PrintTree test = new PrintTree();
        TreeNode instance3 = TreeNode.getInstance4();
        List<List<String>> lists = test.printTree(instance3);

        for (List<String> list : lists) {
            System.out.println(list);
        }
    }

    /*
1：先遍历一次树，获取其最大深度d。
2：所以可以创建一个二维数组arr来记录来记录各个节点。根据树的性质，二维数组的参数为arr[d][(2 << (d - 1)) - 1]用 arr[m][n]。
3：再次遍历树，其根节点的横坐标为n 的中点。
4：之后，前序遍历，子节点和父节点的横坐标的距离为m == 1 ? 1 : (2 << (m - 2))。
5：最后，二维数组转换为list。
     */

    public List<List<String>> printTree(TreeNode root) {
        int d = findD(root);
        int length = (2 << (d - 1)) - 1;
        List<List<String>> all = new ArrayList<>(d);
        String[][] arr = new String[d][length];
        find(root, arr, d - 1, (d == 1 ? 1 : 2 << (d - 2)) - 1);
        for (int i = 0; i < d; i++) {
            List<String> list = new ArrayList<>(length);
            all.add(list);
            String[] strs = arr[d - i - 1];
            for (int j = 0; j < length; j++) {
                list.add(strs[j] == null ? "" : strs[j]);
            }
        }
        return all;
    }

    private void find(TreeNode node, String[][] arr, int m, int n) {
        if (node == null) {
            return;
        }
        arr[m][n] = String.valueOf(node.val);
        int item = m == 1 ? 1 : (2 << (m - 2));
        find(node.left, arr, m - 1, n - item);
        find(node.right, arr, m - 1, n + item);
    }

    private int findD(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return Math.max(findD(node.left), findD(node.right)) + 1;
    }

}
